package jianzhioffer;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/20 22:25
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 *
 * 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。  
 *
 * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
 */
public class offer_11_旋转数组的最小数字 {

    public static void main(String[] args) {
        int[] numbers = {3, 4, 5, 1, 2};
        int res = minArray(numbers);
        System.out.println(res);
    }


//    暴力遍历（不推荐）
    public static int minArray1(int[] numbers) {
        int min = numbers[0];
        for (int i=1; i<numbers.length; i++){
            if (numbers[i]<min) min = numbers[i];
        }
        return min;
    }

//    暴力的基础上二分
    public static int minArray(int[] numbers) {
        int i=0, j=numbers.length-1;
        while (i<j){
            int m = (i+j)/2;
            if (numbers[m] > numbers[j]) i = m+1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
}
